\section{属性约简}
\subsection{属性约简的概念}

\begin{defn}[约简]
    称 $b\subseteq A$ 是 $(U,A,F)$ 的协调集, 若满足 $R_B=R_A$ , 若进一步对任意的 $b\in B$ 都有 $B_{B-\left\{ b \right\}}\ne R_A$ , 称 $B$ 为 $(U,A,F)$ 的约简.
\end{defn}

\begin{framed}
    也就是说, 约简就是属性集 $A$ 的子集, 把一些用处不大的属性去掉了, 剩下的 $B$ 都是有用的属性, 去一个都不行.
\end{framed}

\begin{theorem}
    约简总是存在的.
\end{theorem}

\begin{framed}
    在 $A$ 中如果去不掉没有用的元素, 那 $A$ 本身就是约简, 如果能去一个的话, 比如能去掉 $a\in A$, 那让 $A_1 = A-\left\{ a \right\}$ , 这样再对 $A_1$ 考虑能不能去掉, 如果去不掉那 $A_1$ 就是约简
    , 如果能去掉则继续. 
    
    \textbf{所以约简总是存在的.}
\end{framed}

\begin{theorem}
    约简不一定是唯一的.
\end{theorem}

\begin{example}\label{ex:is}
    信息系统如表 \ref{tab:is}
    
\begin{table}[H]
    \centering
    \caption{信息系统}
    \label{tab:is}
    \setlength{\tabcolsep}{1cm}
    \begin{tabular}{cccc}
        \toprule
        $U$ & $a_1$ & $a_2$ & $a_3$  \\
        \midrule
        $x_1$ & 2 & 1 & 3 \\ 
        $x_2$ & 3 & 2 & 1 \\ 
        $x_3$ & 2 & 1 & 3 \\ 
        $x_4$ & 1 & 1 & 4 \\ 
        $x_5$ & 1 & 1 & 2 \\ 
        $x_6$ & 1 & 1 & 4 \\ 
        $x_7$ & 1 & 2 & 3 \\ 
        $x_8$ & 1 & 2 & 3 \\
        \bottomrule
    \end{tabular}
\end{table}
    令 $A=\left\{ a_1,a_2,a_3 \right\}$ , 则 
    $$ 
    \begin{aligned}R_A = \{ & (x_1,x_1),(x_1,x_3),(x_2,x_2),(x_3,x_1),(x_3,x_3),\\
    & (x_4,x_4),(x_4,x_6),(x_5,x_5),(x_6,x_4),(x_6,x_6),\\
    & (x_7,x_7),(x_7,x_8),(x_8,x_7),(x_8,x_8) \}.
    \end{aligned} $$
    对于属性集 $B_1 = \left\{ a_1,a_3 \right\}$ 和 $B_2 = \left\{ a_2,a_3 \right\}$ ,可得 
    $$ R_{B_1}=R_{B_2}=R_A $$
    但是如果去掉一个元素 
    $$ R_{a_1}\ne R_A, R_{a_2}\ne R_A, R_{a_3}\ne R_A $$
    所以 $B_1\ne B_2$ 都是约简.
\end{example}

\subsection{基础属性约简的方法}
\subsubsection{辨识矩阵的方法}

\begin{defn}[辨识矩阵]\cite{张文修2003信息系统与知识发现}
    设 $(U,A,F)$ 是信息系统, 由 $R_A$ 确定的划分为 
    $$ \mathscr{A}=U/R_A = \left\{ C_i\Big|i\le t \right\} $$
    用 $f_l(C_i)$ 表示属性 $a_l$ 在 $C_i$ 中的值, 称 
    $$ D(C_i,C_j) = \left\{ a_l\in A\Big|f_l(C_i)\ne f_l(C_j) \right\} $$
    为 $C_i$ 和 $C_j$ 的可辨识属性集. 称 
    $$ \mathscr{D}=\left( D(C_i,C_j) \right)_{t\times t} $$
    为信息系统的可辨识矩阵. 
\end{defn}

\begin{example}\label{ex:ezis}
    在例 \ref{ex:is} 中, 我们先简化信息系统得到 
    \begin{table}[H]
        \centering
        \caption{简化后的信息系统}
        \label{tab:ezis}
        \setlength{\tabcolsep}{1cm}
        \begin{tabular}{lccc}
            \toprule
            $\mathscr{A}$                   & $a_1$ & $a_2$ & $a_3$ \\
            \midrule
            $C_1=\left\{ x_1,x_3 \right\}$  & 2     & 1     & 3     \\ 
            $C_2=\left\{ x_2 \right\}    $  & 3     & 2     & 1     \\ 
            $C_3=\left\{ x_7,x_8 \right\}$  & 1     & 2     & 3     \\ 
            $C_4=\left\{ x_4,x_6 \right\}$  & 1     & 1     & 4     \\ 
            $C_5=\left\{ x_5 \right\}    $  & 1     & 1     & 2     \\ 
            \bottomrule
        \end{tabular}
    \end{table}

    辨识矩阵为 
    $$\mathscr{D} = \begin{pmatrix}
        \varnothing               & A                       & \left\{ a_1,a_2 \right\} & \left\{ a_1,a_3 \right\} & \left\{ a_1,a_3 \right\} \\ 
        A                         & \varnothing             & \left\{ a_1,a_3 \right\} & A                        & A                        \\ 
        \left\{ a_1,a_2 \right\}  & \left\{ a_1,a_3 \right\}& \varnothing              & \left\{ a_2,a_3\right\}  & \left\{ a_2,a_3 \right\} \\ 
        \left\{ a_1,a_3 \right\}  & A                       & \left\{ a_2,a_3 \right\} & \varnothing              & \left\{ a_3 \right\}     \\ 
        \left\{ a_1,a_3 \right\}  & A                       & \left\{ a_2,a_3 \right\} & \left\{ a_3 \right\}     & \varnothing              \\
    \end{pmatrix}$$
\end{example}

\begin{defn}[辨识公式]
    对于信息系统的辨识矩阵 $\mathscr{D}$ , 辨识公式为 
    $$ M = \bigwedge_{i\ne j}\left( \bigvee D(C_i,C_j) \right). $$
    化简为合取范式后的辨识公式 
    $$ M = \bigvee_{k=1}^p\left( \bigwedge_{l=1}^{q_k}a_{i_l} \right) $$
    称为最小表达式, 如果 $B_k=\left\{ a_{i_l}\Big|l\le q_k \right\}$ 中无重复元素.
\end{defn}

\begin{theorem}
    设 $(U,A,F)$ 是信息系统, $\mathscr{A}=\left\{ C_i\Big|i\le t \right\}$ 是由 $R_A$ 产生的 $U$ 上的划分, $M$ 是 $\mathscr{A}$ 的辨识公式, 则 $M$ 的最小表达式的每一项形成的
    $$ B_k=\left\{ a_{i_l}\Big|l\le q_k \right\}, (k\le p) $$
    是信息系统的约简, 且 $B_k (k\le p)$ 是所有约简.
\end{theorem}

\begin{example}
    在例 \ref{ex:ezis} 中, 辨识公式为 
    $$ M=a_3\wedge(a_1\vee a_2)\wedge(a_1\vee a_3)\wedge(a_2\vee a_3)\wedge(a_1\vee a_2\vee a_3). $$
    化简为合取范式:
    $$ M = (a_1\wedge a_3)\vee (a_2\wedge a_3). $$
    最后得到 $\left\{ a_1,a_3 \right\}$ 和 $\left\{ a_2,a_3 \right\}$ 是所有的约简.
\end{example}

\subsubsection{辨识矩阵做属性约简的实验}

关于辨识矩阵我设计了一个算法 \ref{al:bsjz} 去利用辨识矩阵做属性约简,
\input{algorithm/bsjz.tex}

利用这个算法写的Python程序运行结果如图 \ref{fig:bsjz}: 输入的表为表 \ref{tab:is}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.9\linewidth]{figures/is_bsjz.png}
    \caption{辨识矩阵算法运行结果}
    \label{fig:bsjz}%文中引用该图片代号
\end{figure}

\subsubsection{启发式算法做属性约简}
首先, 什么叫做启发式算法? 启发式算法 (Heuristic Algorithms) 是相对于最优算法提出的。一个问题的最优算法是指求得该问题每个实例的最优解. 启发式算法可以这样定义
\begin{defn}[启发式算法]\cite{邢文训2005现代优化计算方法}
    一个基于直观或经验构造的算法，在可接受的花费 (指计算时间、占用空间等) 下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计.
\end{defn}


首先我们利用启发式算法做属性约简时需要一些正域、依赖函数、重要程度的概念:

\begin{defn}[正域, 依赖度, 重要度]
    信息系统 $(U,C\bigcup D,V,F)$ , 设 $U/D=\left\{ D_1,D_2,\cdots,D_l \right\}$ , $|U|=n$ .称 
    $$ {\rm Pos}_C(D)=\bigcup_{k=1}^l\underline{R_C}D_k $$
    为决策属性 $D$ 相对于条件属性集合 $C$ 的正域. 称 
    $$ \gamma_C(D)=\frac{1}{n}|{\rm Pos}_C(D)|=\frac{1}{n}\sum_{k=1}^l |\underline{R_C}D_k| $$
    为决策属性 $D$ 相对于条件属性集合 $C$ 的依赖函数.任取 $a\in C$ ,定义 $a$ 的重要程度 $sign_C(a,D)$ 为 
    $$ sign_C(a,D)=\gamma_C(D) - \gamma_{C-\left\{ a \right\}}(D) $$
\end{defn}

\begin{defn}
    设 $(U,C\bigcup D)$ 是一个完备决策系统, 对 $\forall a\in C$, 若 $\pos_{C-\left\{ a \right\}}(D)=\pos_C(D)$, 则称 $a$ 在 $C$ 中相对 $D$ 不必要, 
    否则称 $a$ 在 $C$ 中相对 $D$ 必要. 对于 $P\subseteq C$ , 如果有 $\pos_{P}(D)=\pos_C(D)$ 且 $P$ 中任何一个条件属性在 $P$ 中相对于 $D$ 都必要, 则称
     $P$ 是 $C$ 的一个相对 $D$ 的属性约简.  $C$ 中相对 $D$ 的全部必要属性集合称为 $C$ 相对 $D$ 的核心, 记为 ${\rm Core}_C(D)$ . 如果用 ${\rm RED}_C(D)$ 
     表示 $C$ 的相对 $D$ 的全部属性约简集合, 则易证 ${\rm Core}_C(D)$ 恰好是全部属性约简的交集, 即  ${\rm Core}_C(D)=\bigcap {\rm RED}_C(D)$. 
\end{defn}


算法如算法 \ref{al:ylhs}, 输入数据如表 \ref{tab:ylhs_is}
\begin{table}[!h]
    \centering
    \caption{信息系统}
    \label{tab:ylhs_is}
    \setlength{\tabcolsep}{1cm}
    \begin{tabular}{cccc}
        \toprule
        a1 & a2 & a3 & d \\ 
        \midrule
        2 & 1 & 3 & 1 \\ 
        3 & 2 & 1 & 2 \\ 
        2 & 1 & 3 & 1 \\ 
        2 & 2 & 3 & 2 \\ 
        1 & 1 & 4 & 3 \\ 
        1 & 1 & 2 & 3 \\ 
        3 & 2 & 1 & 2 \\ 
        1 & 1 & 4 & 3 \\ 
        2 & 1 & 3 & 1 \\ 
        3 & 2 & 1 & 2 \\ 
        \bottomrule
    \end{tabular}
\end{table}
\input{algorithm/rely_function.tex}

利用这个算法写的Python程序运行结果如图 \ref{fig:ylhs}
\begin{figure}[H]
    \centering
	\includegraphics[width=0.9\linewidth]{figures/yilaihanshu.png}
	\caption{依赖函数算法运行结果}
	\label{fig:ylhs}%文中引用该图片代号
\end{figure}

\input{sections/加权模糊粗糙集属性约简.tex}
\input{sections/基于优势领域粗糙集的有序数据特征提取.tex}